1. Field of the Invention
The present invention relates to an inference processing system used for an expert system, etc., and particularly to an inference processing system using a plurality of processors to carry out a parallel inference operation.
2. Description of the Prior Art
Recently, studies are enthusiastically being done on expert systems that utilize computers to substitute for the roles of experts in various fields. The expert systems store knowledges of the experts in the computers and use the stored knowledges to infer conclusions.
As an example of the inference, a way of description by a Prolog which is one programming language suitable for the inference will be described.
A program written with the Prolog comprises facts and rules.
The facts are descriptions of relations between things. For instance, a fact "Taro is father of Ichiro" is described with a predicate "father" and arguments "Taro" and "Ichiro" as follows:
father (Taro, Ichiro).
The rules are the expressions of knowledges such as "if A then B". The rules are described by replacing the arguments "Taro" and "Ichiro" with variables "X" and "Z" for example as follows:
______________________________________ grandfather (X, Y):- father (X, Z), father (Z, Y) ______________________________________
This rule means that "if X is father of Z and if Z is father of Y, then X is grandfather of Y".
Generally, an execution of the program written with the Prolog is ended when a given goal is matched (unified) with certain facts. Even if the given goal and the facts are not unified at first, the given goal is unified with respect to the left side of a rule. When the goal is unified with the left side of the rule, the right side of the rule will be set as a new goad that is to be again unified with respect to the left side of the rule. This operation is repeated. When the goal is unified with respect to the facts, the execution of the program is ended.
______________________________________ Rule 1: grandfather (X, Y):- father (X, Z), father (Z, Y) Fact 1: father (Taro, Ichiro) Fact 2: father (Taro, Jiro) Fact 3: father (Ichiro, Saburo) Fact 4: father (Ichiro, Shiro) Fact 5: father (Jiro, Goro) Fact 6: father (Jiro, Rokuro) ______________________________________
If a goal "grandfather (Taro, Y)" that means "whose grandfather Taro is" is given, the goal is unified collated with the left side of the rule 1 to get X=Taro. This is substituted for the right side of the rule 1 to present a new goal "father (Taro, Z), father (Z, Y)". The front half "father (Taro, Z)" of this new goal and the rule 1 are unified to find Z=Ichiro. This is substituted for the new goal to obtain "father (Taro, Ichiro), father (Ichiro, Z)". Then, the rear half "father (Ichiro, Y)" of the new goal and the fact 3 are unified to obtain Y=Saburo. As a result, one solution "grandfather (Taro, Saburo)" is obtained.
The above-mentioned process is a way to obtain the one solution. To obtain all solutions satisfying the first goal "grandfather (Taro, Y)", a back tracking operation shall further be carried out. Namely, the substitution of "Y=Saburo" obtained in the above-mentioned process is canceled to find another solution that is unified with respect to the middle goal "father (Ichiro, Y)". Then, this goal and the fact 4 are unified to obtain a new solution of Y=Shiro. In this way, the substitutions for the variables are successively canceled to find other solutions, i.e., Y=Goro and Y=Rokuro.
The facts used in this example may be expressed with a semantic network shown in FIG. 1. In the semantic network, the arguments of predicates are expressed as nodes of the network respectively, and the predicates indicating relations between the arguments are represented with links between the nodes. In FIG. 1, the rule 1 is translated that a grandfather link is equivalent to two stages of father links.
To search all solutions for a goal according to the above-mentioned back tracking, the substitution and back tracking shall be frequently repeated on the respective links of the semantic network. Therefore: a time needed for executing the Prolog program is extended to hinder high-speed processing.
As described in the above, the conventional inference system searches all solutions to a goal through sequential processing where the substitution and back tracking are repeated frequently to increase an amount of knowledges to be handled and extremely elongate an execution time of the program.